package com.exercises;

public class Exercise208 {
    public static void main(String[] args) {
        char a = 'z';
        System.out.println(a - 'a');
    }

    class Trie {
        private Trie[] childs;
        private boolean end;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            childs = new Trie[26];
            end = false;
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            Trie trie = this;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (trie.childs[index] == null) {
                    trie.childs[index] = new Trie();
                }
                trie = trie.childs[index];
            }
            trie.end = true;
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            Trie trie = findPrefix(word);
            return trie != null && trie.end;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return findPrefix(prefix) != null;
        }


        public Trie findPrefix(String prefix) {
            Trie trie = this;
            for (char c : prefix.toCharArray()) {
                int index = c - 'a';
                if (trie.childs[index] == null) {
                    return null;
                }
                trie = trie.childs[index];
            }
            return trie;
        }
    }
}
